# 二维前缀和， 二维差分
class Solution(object):
    def possibleToStamp(self, grid, stampHeight, stampWidth):
        m = len(grid)
        n = len(grid[0])
        prefix = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                prefix[i][j] = prefix[i][j - 1] + prefix[i - 1][j] - prefix[i - 1][j - 1] + (grid[i - 1][j - 1] == 0)
        diff = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if i >= stampHeight and j >= stampWidth:
                    last_i = i - stampHeight
                    last_j = j - stampWidth
                    if prefix[i][j] - prefix[last_i][j] - prefix[i][last_j] + prefix[last_i][last_j] == stampHeight * stampWidth:
                        diff[last_i + 1][last_j + 1] += 1
                        if i < m:
                            diff[i + 1][last_j + 1] -= 1
                        if j < n:
                            diff[last_i + 1][j + 1] -= 1
                        if i < m and j < n:
                            diff[i + 1][j + 1] += 1
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                diff[i][j] += diff[i - 1][j] + diff[i][j - 1] - diff[i - 1][j - 1]
                if grid[i - 1][j - 1] == 0 and diff[i][j] == 0:
                    return False
        return True





data = Solution()
grid = [[1,0,0,0],[0,1,0,0],[0,0,1,0],[0,0,0,1]]
stampHeight = 2
stampWidth = 2
print(data.possibleToStamp(grid, stampHeight, stampWidth))
grid = [[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0],[1,0,0,0]]
stampHeight = 4
stampWidth = 3
print(data.possibleToStamp(grid, stampHeight, stampWidth))
grid = [[1,0,1],[0,0,0]]
stampHeight = 2
stampWidth = 1
print(data.possibleToStamp(grid, stampHeight, stampWidth))